def insertion_sort(arr):
    """插入排序"""
    comparisons = 0
    swaps = 0
    
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0:
            comparisons += 1
            if arr[j] > key:
                arr[j + 1] = arr[j]
                swaps += 1
                j -= 1
            else:
                break
        arr[j + 1] = key
    
    return {
        'sorted_array': arr,
        'comparisons': comparisons,
        'swaps': swaps,
        'time_complexity': 'O(n²)'
    }

def bubble_sort(arr):
    """冒泡排序"""
    comparisons = 0
    swaps = 0
    n = len(arr)
    
    for i in range(n):
        for j in range(0, n - i - 1):
            comparisons += 1
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swaps += 1
    
    return {
        'sorted_array': arr,
        'comparisons': comparisons,
        'swaps': swaps,
        'time_complexity': 'O(n²)'
    }

def quick_sort(arr):
    """快速排序（迭代实现）"""
    comparisons = 0
    swaps = 0
    
    def partition(low, high):
        nonlocal comparisons, swaps
        pivot = arr[high]
        i = low - 1
        
        for j in range(low, high):
            comparisons += 1
            if arr[j] <= pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]
                swaps += 1
        
        arr[i + 1], arr[high] = arr[high], arr[i + 1]
        swaps += 1
        return i + 1
    
    # 使用栈来模拟递归
    stack = []
    stack.append((0, len(arr) - 1))
    
    while stack:
        low, high = stack.pop()
        if low < high:
            pi = partition(low, high)
            # 将较大的子数组先入栈，这样可以减少栈的深度
            if pi - low > high - pi:
                stack.append((low, pi - 1))
                stack.append((pi + 1, high))
            else:
                stack.append((pi + 1, high))
                stack.append((low, pi - 1))
    
    return {
        'sorted_array': arr,
        'comparisons': comparisons,
        'swaps': swaps,
        'time_complexity': 'O(n log n)'
    }

def heap_sort(arr):
    """堆排序"""
    comparisons = 0
    swaps = 0
    
    def heapify(n, i):
        nonlocal comparisons, swaps
        largest = i
        left = 2 * i + 1
        right = 2 * i + 2
        
        comparisons += 1
        if left < n and arr[left] > arr[largest]:
            largest = left
        
        comparisons += 1
        if right < n and arr[right] > arr[largest]:
            largest = right
        
        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]
            swaps += 1
            heapify(n, largest)
    
    n = len(arr)
    
    # 构建最大堆
    for i in range(n // 2 - 1, -1, -1):
        heapify(n, i)
    
    # 一个个交换元素并维护堆的性质
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        swaps += 1
        heapify(i, 0)
    
    return {
        'sorted_array': arr,
        'comparisons': comparisons,
        'swaps': swaps,
        'time_complexity': 'O(n log n)'
    }

def is_sorted(arr):
    """检查数组是否已排序"""
    return all(arr[i] <= arr[i + 1] for i in range(len(arr) - 1)) 